#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/***************************************************************
 *函数名称：help_tree
 *函数功能：输出二叉树的操作菜单
 *返回值类型：void
 ****************************************************************/
void help_tree(void) {
    printf("    1 :创建二叉树\n");
    printf("    2 :清空二叉树\n");
    printf("    3 :求二叉树深度\n");
    printf("    4 :查找结点\n");
    printf("    5 :结点赋值\n");
    printf("    6 :获得兄弟结点\n");
    printf("    7 :插入结点\n");
    printf("    8 :删除结点\n");
    printf("    9 :先序遍历\n");
    printf("    10:中序遍历\n");
    printf("    11:后序遍历\n");
    printf("    12:按层遍历\n");
    printf("    13:二叉树读入文件\n");
    printf("    14:二叉树读取文件\n");
    printf("    15:最大路径和\n");
    printf("    16:翻转二叉树\n");
    printf("    17:菜单\n");
    printf("    18:二叉树判空\n");
    printf("    0 :退出\n");
}

/***************************************************************
 *函数名称：help_list
 *函数功能：输出多表的操作菜单
 *返回值类型：void
 ****************************************************************/
void help_list(void) {
    printf("    1:新建一个二叉树\n");
    printf("    2:删除一个二叉树\n");
    printf("    3:查找一个二叉树\n");
    printf("    4:菜单\n");
    printf("    0:退出\n");
}

/***************************************************************
 *函数名称：CreateBiTree
 *函数功能：根据带空枝的二叉树先根遍历序列definition构造一棵二叉树，将根节点指针赋值给T并返回OK，如果有相同的关键字，返回ERROR。
 *返回值类型：status
 ****************************************************************/
int ii = 0;
status CreateBiTree(BiTree &T, TElemType definition[]) {
    int len = 0; //求数组长度
    while (definition[len].key != -1)
        len++;
    for (int a = 0; a < len; a++) {
        if (definition[a].key == 0)
            continue;
        for (int j = 0; j < a; j++) {
            if (definition[j].key == 0)
                continue;
            if (definition[j].key == definition[a].key)
                return ERROR;
        }
    } //判断数据是否合法
    if (-1 == definition[ii].key)
        return INFEASIBLE;
    if (definition[ii].key == 0) {
        T = NULL;
        ii++;
        return OK;
    } else {
        T = (BiTree)malloc(sizeof(BiTNode));
        T->data.key = definition[ii].key;
        strcpy(T->data.others, definition[ii++].others);
    }
    CreateBiTree(T->lchild, definition);
    CreateBiTree(T->rchild, definition);
    return OK;
}

/***************************************************************
 *函数名称：DestroyBiTree
 *函数功能：销毁二叉树
 *返回值类型：status
 ****************************************************************/
status DestroyBiTree(BiTree &T) {
    if (T) {
        DestroyBiTree(T->lchild);
        DestroyBiTree(T->rchild);
        free(T);
        T = NULL;
    }
    return OK;
}

/***************************************************************
 *函数名称：ClearBiTree
 *函数功能：将二叉树设置成空，并删除所有结点，释放结点空间
 *返回值类型：status
 ****************************************************************/
status ClearBiTree(BiTree &T) {

    if (T) {
        //判断是否左节点
        if ((T)->lchild)
            ClearBiTree((T)->lchild);
        //判断是否右节点
        if ((T)->rchild)
            ClearBiTree((T)->rchild);
        free(T);
        T = NULL;
    }
    return OK;
}

/***************************************************************
 *函数名称：BiTreeEmpty
 *函数功能：判断二叉树是否为空,为空返回true 否则返回false
 *返回值类型：status
 ****************************************************************/
status BiTreeEmpty(BiTree T) {
    if (T == NULL)
        return TRUE;
    else
        return FALSE;
}

/***************************************************************
 *函数名称：BiTreeDepth
 *函数功能：求二叉树T的深度
 *返回值类型：int
 ****************************************************************/
int BiTreeDepth(BiTree T) {
    if (T == NULL)
        return 0;
    int m, n;
    m = BiTreeDepth(T->lchild); //返回左子树深度
    n = BiTreeDepth(T->rchild); //返回右子树深度
    return m > n ? m + 1 : n + 1;
}

/***************************************************************
 *函数名称：LocateNode
 *函数功能：查找结点
 *返回值类型：BiTNode *
 ****************************************************************/
BiTNode *LocateNode(BiTree T, KeyType e) {
    if (T == NULL)
        return NULL;
    BiTree P = NULL;
    if (T->data.key == e) {
        P = T;
        return P;
    }
    BiTree q;
    q = LocateNode(T->lchild, e); //查找左子树
    if (q != NULL)
        P = q;
    q = LocateNode(T->rchild, e); //查找右子树
    if (q != NULL)
        P = q;
    return P;
}

/***************************************************************
 *函数名称：Assign
 *函数功能：实现结点赋值
 *返回值类型：status
 ****************************************************************/
int flag = 1;
status Assign(BiTree &T, KeyType e, TElemType value) {
    int p = 0;
    if (T == NULL)
        return p;
    if (T->data.key == value.key && T->data.key != e)
        flag = 0;
    if (T->data.key == e) {
        T->data.key = value.key;
        strcpy(T->data.others, value.others);
        p = 1;
    }
    int tem;
    tem = Assign(T->lchild, e, value);
    p = p > tem ? p : tem;
    tem = Assign(T->rchild, e, value);
    p = p > tem ? p : tem;
    if (flag == 0)
        return 0; // flag=0表明没有找到
    else
        return p;
}

/***************************************************************
 *函数名称：GetSibling
 *函数功能：实现获得兄弟结点
 *返回值类型：BiTNode *
 ****************************************************************/
BiTNode *GetSibling(BiTree T, KeyType e) {
    BiTree p = NULL, q = NULL;
    if (T == NULL)
        return p;
    if (T->lchild != NULL && T->lchild->data.key == e && T->rchild != NULL) {
        p = T->rchild;
        // return p;
    }
    if (T->rchild != NULL && T->rchild->data.key == e && T->lchild != NULL) {
        p = T->lchild;
        // return p;
    }
    q = GetSibling(T->lchild, e);
    if (q != NULL)
        p = q;
    q = GetSibling(T->rchild, e);
    if (q != NULL)
        p = q;
    return p;
}

/***************************************************************
 *函数名称：InsertNode
 *函数功能：插入结点。
 *返回值类型：status
 ****************************************************************/
status InsertNode(BiTree &T, KeyType e, int LR, TElemType c) {
    if (T == NULL)
        return ERROR;
    int flag = 0;
    if (LR == -1 && T != NULL) { //插入到根节点
        BiTree p;
        p = (BiTree)malloc(sizeof(BiTNode));
        p->data.key = c.key;
        strcpy(p->data.others, c.others);
        p->lchild = NULL;
        p->rchild = T;
        T = p;
        return OK;
    }
    if (T->data.key == c.key)
        return flag;
    if (T->data.key == e) { //找到了这个结点
        BiTree p;
        p = (BiTree)malloc(sizeof(BiTNode));
        p->data.key = c.key;
        strcpy(p->data.others, c.others);
        p->lchild = NULL;
        if (LR == 0) {
            p->rchild = T->lchild;
            T->lchild = p;
        } else if (LR == 1) {
            p->rchild = T->rchild;
            T->rchild = p;
        }
        return OK;
    }
    int i;
    i = InsertNode(T->lchild, e, LR, c);
    flag = i > 0 ? i : 0;
    i = InsertNode(T->rchild, e, LR, c);
    flag = i > 0 ? i : 0;
    return flag;
}

/***************************************************************
 *函数名称：DeleteNode
 *函数功能：删除结点。
 *返回值类型：status
 ****************************************************************/
status DeleteNode(BiTree &T, KeyType e) {
    if (T == NULL)
        return ERROR;
    BiTree p;
    if (T->data.key == e) {
        p = T;
        if (p->lchild && p->rchild) {
            BiTree q = p->lchild;
            while (q->rchild != NULL) {
                q = q->rchild;
            }
            q->rchild = T->rchild;
        }
        T = T->lchild;
        free(p);
        return OK;
    }
    if (T->lchild && T->lchild->data.key == e) {
        p = T->lchild;
        if (p->lchild && p->rchild) {
            T->lchild = p->lchild;
            BiTree q = p->lchild;
            while (q->rchild != NULL) {
                q = q->rchild;
            }
            q->rchild = p->rchild;
        } else if (p->lchild && !p->rchild) {
            T->lchild = p->lchild;
        } else if (p->rchild && !p->lchild) {
            T->lchild = p->rchild;
        } else if (!p->lchild && !p->rchild) {
            T->lchild = NULL;
        }
        free(p);
        return OK;
    } else if (T->rchild && T->rchild->data.key == e) {
        p = T->rchild;
        if (p->lchild && p->rchild) {
            T->lchild = p->lchild;
            BiTree q = p->lchild;
            while (q->rchild != NULL) {
                q = q->rchild;
            }
            q->rchild = p->rchild;
        } else if (p->lchild && !p->rchild) {
            T->rchild = p->lchild;
        } else if (p->rchild && !p->lchild) {
            T->rchild = p->rchild;
        } else if (!p->lchild && !p->rchild) {
            T->rchild = NULL;
        }
        free(p);
        return OK;
    }
    int i, flag = 0;
    i = DeleteNode(T->lchild, e);
    flag = i > 0 ? i : 0;
    i = DeleteNode(T->rchild, e);
    flag = i > 0 ? i : 0;
    return flag;
}

/***************************************************************
 *函数名称：visit
 *函数功能：访问结点数据
 *返回值类型：void
 ****************************************************************/
void visit(BiTree T) {
    printf(" %d,%s", T->data.key, T->data.others);
}

/***************************************************************
 *函数名称：PreOrderTraverse
 *函数功能：先序遍历二叉树T
 *返回值类型：status
 ****************************************************************/
status PreOrderTraverse(BiTree T, void (*visit)(BiTree)) {
    if (T == NULL)
        return INFEASIBLE;
    visit(T);
    PreOrderTraverse(T->lchild, visit);
    PreOrderTraverse(T->rchild, visit);
    return OK;
}

/***************************************************************
 *函数名称：InOrderTraverse
 *函数功能：中序遍历二叉树T
 *返回值类型：status
 ****************************************************************/
status InOrderTraverse(BiTree T, void (*visit)(BiTree)) {
    if (T == NULL)
        return INFEASIBLE;
    InOrderTraverse(T->lchild, visit);
    visit(T);
    InOrderTraverse(T->rchild, visit);
    return OK;
}

/***************************************************************
 *函数名称：PostOrderTraverse
 *函数功能：后序遍历二叉树T
 *返回值类型：status
 ****************************************************************/
status PostOrderTraverse(BiTree T, void (*visit)(BiTree)) {
    if (T == NULL)
        return INFEASIBLE;
    PostOrderTraverse(T->lchild, visit);
    PostOrderTraverse(T->rchild, visit);
    visit(T);
    return OK;
}

/***************************************************************
 *函数名称：LevelOrderTraverse
 *函数功能：按层遍历二叉树T
 *返回值类型：status
 ****************************************************************/
status LevelOrderTraverse(BiTree T, void (*visit)(BiTree)) {
    if (T == NULL)
        return INFEASIBLE;
    BiTree list[100], p; //用一个队列完成这个函数
    int i = 0, j = 1;
    list[0] = T;
    while (i != j) {
        p = list[i];
        i++;
        visit(p);
        if (p->lchild) {
            list[j] = p->lchild;
            j++;
        }
        if (p->rchild) {
            list[j] = p->rchild;
            j++;
        }
    }
    return OK;
}

FILE *fp;
status SaveBiTree1(BiTree T, char FileName[], BiTNode *root)
//将二叉树的结点数据写入到文件FileName中
{
    if (T == root)
        fp = fopen(FileName, "w");
    if (fp == NULL) {
        return ERROR;
    }
    if (T == NULL) {
        fprintf(fp, "%d %s ", 0, "NULL");
        return INFEASIBLE;
    }
    fprintf(fp, "%d %s ", T->data.key, T->data.others);
    SaveBiTree1(T->lchild, FileName, root);
    SaveBiTree1(T->rchild, FileName, root);
    if (T == root)
        fclose(fp);
    return OK;
}

/***************************************************************
 *函数名称：SaveBiTree
 *函数功能：二叉树读入文件
 *返回值类型：status
 ****************************************************************/
status SaveBiTree(BiTree T, char FileName[]) {
    return SaveBiTree1(T, FileName, T);
}

/***************************************************************
 *函数名称：LoadBiTree
 *函数功能：读取文件FileName的结点数据，创建二叉树
 *返回值类型：status
 ****************************************************************/
status LoadBiTree(BiTree &T, char FileName[]) {
    if (T != NULL)
        DestroyBiTree(T);
    fp = fopen(FileName, "r");
    if (fp == NULL)
        return ERROR;
    TElemType definition[100];
    int ans, i = 0;
    while (!feof(fp)) {
        fscanf(fp, "%d %s ", &definition[i].key, definition[i].others);
        // fscanf(fp, "%d %s ", &definition[i++].key, definition[i].others);
        i++;
    }
    fclose(fp);
    definition[i].key = -1;
    strcpy(definition[i].others, "NULL");
    ii = 0;
    ans = CreateBiTree(T, definition);
    return OK;
}

/***************************************************************
 *函数名称：MaxPathSum
 *函数功能：初始条件是二叉树T存在；操作结果是返回根节点到叶子结点的最大路径和
 *返回值类型：status
 ****************************************************************/
int len, tem, prenum;
int MaxPathSum(BiTree T) {
    if (T == NULL) {
        return 0;
    }
    prenum = T->data.key;
    tem += prenum;
    if (!T->lchild && !T->rchild) {
        len = len > tem ? len : tem;
    }
    if (T->lchild) {
        MaxPathSum(T->lchild);
        tem -= prenum;
    }
    if (T->rchild) {
        MaxPathSum(T->rchild);
        tem -= prenum;
    }
    return len;
}

/***************************************************************
 *函数名称：InvertTree
 *函数功能：操作结果是将T翻转，使其所有节点的左右节点互换；
 *返回值类型：status
 ****************************************************************/
status InvertTree(BiTree T) {
    if (T == NULL) {
        return ERROR;
    }
    BiTree newT;
    newT = T->lchild;
    T->lchild = T->rchild;
    T->rchild = newT;
    newT = (BiTree)malloc(sizeof(BiTNode));
    InvertTree(T->lchild); //翻转左子树
    InvertTree(T->rchild); //翻转右子树
    return OK;
}

/***************************************************************
 *函数名称：createlist
 *函数功能：向多表中新建一个二叉树
 *返回值类型：status
 ****************************************************************/
status createlist(LIST &lists, char Filename[]) {
    if (lists.length == 10)
        return OVERFLOW;
    strcpy(lists.elem[lists.length].name, Filename);
    printf("请输入数据用0 NULL表示空结点 -1 NULL 表示结尾\n");
    TElemType definition[100];
    int ans, i = 0;
    do {
        scanf("%d%s", &definition[i].key, definition[i].others);
    } while (definition[i++].key != -1);
    ii = 0;
    CreateBiTree(lists.elem[lists.length].T, definition);
    lists.length++;
    return OK;
}

/***************************************************************
 *函数名称：deletelist
 *函数功能：在多表中删除一个二叉树
 *返回值类型：status
 ****************************************************************/
status deletelist(LIST &lists, char Filename[]) {
    if (lists.length == 0)
        return INFEASIBLE;
    int i = 0;
    for (i; i < lists.length; i++) {
        if (!strcmp(Filename, lists.elem[i].name)) {
            break;
        }
    }
    DestroyBiTree(lists.elem[i].T);
    i++;
    for (i; i < lists.length; i++) {
        strcpy(lists.elem[i - 1].name, lists.elem[i].name);
        lists.elem[i - 1].T = lists.elem[i].T;
    }
    lists.length--;
    return OK;
}

/***************************************************************
 *函数名称：checklits
 *函数功能：在多表中查找一个二叉树
 *返回值类型：status
 ****************************************************************/
int checklits(LIST lists, char filename[]) {
    if (lists.length == 0)
        return ERROR;
    int i = 0;
    for (i; i < lists.length; i++) {
        if (!strcmp(lists.elem[i].name, filename)) {
            break;
        }
    }
    if (i == lists.length)
        return -1;
    else
        return i + 1;
}